#include <iostream>
#include <vector>
#include <string>
#include <iostream>
#include <unordered_map>
#include <set>
#include <map>

using namespace std;

// https://leetcode.cn/problems/lexicographically-smallest-equivalent-string/description/?envType=daily-question&envId=2025-06-05
// 1061. 按字典序排列最小的等效字符串

class Solution
{
public:
    // 错误解法
    string smallestEquivalentString(string s1, string s2, string baseStr)
    {
        map<char, set<char>> recordGraph;
        for (int i = 0; i < s1.size(); i++){
            recordGraph[s1[i]].insert(s2[i]);
            recordGraph[s2[i]].insert(s1[i]);
        }
        for(auto it : recordGraph){
            char minCh = it.first;
            minCh = min(minCh, *it.second.begin());
            for (auto node : it.second)
            {
                recordGraph[node].insert(minCh);
            }
        }
        string ans;
        for(char ch : baseStr){
            ans += min(ch, *recordGraph[ch].begin());
        }
        return ans;
    }
};

int main()
{
    string s1 = "leetcode";
    string s2 = "programs";
    string s3 = "sourcecode";
    Solution solution{};
    cout << solution.smallestEquivalentString(s1, s2, s3) << endl;
    return 0;
}